📚 课程模块：分布式数据库系统 (Distributed Databases)#

1. 核心概念解释#

分布式数据库旨在将单一节点的数据库功能扩展到多台机器上，以实现更高的性能、存储容量或高可用性。

• Shared Nothing (无共享架构)：每个节点拥有独立的 CPU、内存和磁盘。节点间通过网络通信，不仅无法直接访问其他节点的内存，也不能直接访问其他节点的磁盘。这是 80-90 年代和早期 NoSQL 系统的主流架构。
• Shared Disk (共享磁盘架构)：所有计算节点拥有独立的 CPU 和内存，但共享同一个远程存储层（如 Amazon S3, HDFS）。计算节点是无状态的（Stateless），数据持久化在共享存储层。这是现代云原生数据库（如 Snowflake, Aurora）的主流架构。

2. 关键结论 / 公式 / 方法#

• 性能对比：Shared Nothing 通常能获得最佳性能，因为数据就在本地，减少了网络开销；但扩容（Scaling）较难，需要迁移数据。
• 扩容便利性：Shared Disk 扩容非常容易，只需增加计算节点并更新元数据（Catalog），无需物理移动数据。
• Shared Memory：理论上存在，但实际上除了高性能计算（HPC）外极少使用。

3. 易混点或易错点提示#

• ⚠️ 误区：认为 Shared Disk 意味着多个节点同时写入同一个物理硬盘块而没有任何协调。纠正：实际上节点间仍需通过锁或所有权机制来协调写入，否则会破坏数据一致性。
• ⚠️ 区分：Shared Disk 架构中，计算节点可能有本地缓存（Local Cache/SSD），但这仅作缓存用，非数据最终持久化位置。

4. 简短复习小结#

• Shared Nothing = 独立资源，高性能，扩容难。
• Shared Disk = 独立计算 + 共享存储，云原生首选，扩容易。

1. 核心概念解释#

为了将数据分布到不同节点，需要对表进行水平分片（Horizontal Partitioning / Sharding）。

• Hash Partitioning (哈希分片)：hash(key) % N。
• Range Partitioning (范围分片)：根据 Key 的值域区间分配（如 ID 1-100 在节点 A）。
• Consistent Hashing (一致性哈希)：解决节点增减导致大规模数据迁移的问题。将节点和数据都映射到一个圆环上，数据沿顺时针方向由遇到的第一个节点负责。

2. 关键结论 / 公式 / 方法#

• 一致性哈希优势：当添加/移除节点时，只需重新分配圆环上相邻节点的一小部分数据，而不是重新哈希整个数据库。
• Rendezvous Hashing：为每个 Key 计算 hash(key + node_id)，选择哈希值最大的节点。这提供了比一致性哈希更均衡的负载分布，且查找复杂度为 O(N)（实际上通过优化可更快，但讲义中提及相比一致性哈希可能有特定优势）。

3. 易混点或易错点提示#

• ⚠️ 陷阱：简单的 Hash % N 分片在节点数 N 变化时，会导致几乎所有数据的位置发生改变（Rebalancing cost 极高）。
• ⚠️ 细节：一致性哈希中，为了解决数据倾斜（Skew），通常会引入虚拟节点 (Virtual Nodes)，即一个物理节点在圆环上对应多个位置。

4. 简短复习小结#

• 普通哈希分片适合查询但不适合扩容。
• 一致性哈希是分布式系统（如 Dynamo, Cassandra）处理节点动态变化的标准解法。

1. 核心概念解释#

在分布式事务（OLTP）中，必须保证所有节点对事务的提交结果达成一致（要么全提交，要么全回滚）。

• Two-Phase Commit (2PC, 两阶段提交)：经典的阻塞式协议。
  • Phase 1 (Prepare): 协调者询问所有参与者“可以提交吗？”。
  • Phase 2 (Commit/Abort): 如果所有人都回复 Yes，则发送 Commit；只要有一个 No，则发送 Abort。
• Paxos / Raft (共识协议)：基于“多数派”（Majority）存活即可工作的非阻塞协议。

2. 关键结论 / 公式 / 方法#

• 2PC 的致命弱点：如果协调者（Coordinator）或某个参与者在关键时刻崩溃，系统可能会阻塞（Blocking），等待节点恢复才能释放锁。
• Paxos/Raft 的优势：只需要 N/2 + 1 个节点同意即可推进系统状态（Non-blocking）。如果少数节点宕机，系统仍可用。
• 优化：
  • Early Acknowledgement：一旦协调者在第一阶段收到所有人的“Yes”，即便第二阶段还未完成，也可以提前告诉客户端“提交成功”，随后在后台完成第二阶段。

3. 易混点或易错点提示#

• ⚠️ 易混淆：2PC 要求全员 (All) 同意，Paxos/Raft 只要 多数派 (Majority) 同意。2PC 是 Paxos 的一种退化特例。
• ⚠️ 误区：认为区块链也是数据库常用的协议。纠正：区块链解决的是“拜占庭容错”（Byzantine Fault Tolerance，即节点可能恶意撒谎），而数据库内部假设节点是良性但可能崩溃的，因此不需要如此昂贵的协议。

4. 简短复习小结#

• 2PC = 强一致性，但在节点故障时会阻塞。
• Paxos/Raft = 容错性更好，只要多数派存活即可工作。

1. 核心概念解释#

Eric Brewer 提出的理论，指出分布式数据系统无法同时满足以下三点：

• Consistency (一致性)：所有节点看到的数据是一样的。
• Availability (可用性)：每次请求都能收到非错误的响应（无论节点是否宕机）。
• Partition Tolerance (分区容错性)：在网络分区（节点间无法通信）发生时，系统仍能运行。

2. 关键结论 / 公式 / 方法#

• 2选1 困境：在网络分区（P）必然可能发生的前提下，你只能在 C 和 A 之间做选择。
  • CP (选择一致性)：网络分区时，为了保证数据不冲突，停止服务（不可用）。传统关系型数据库通常选这个。
  • AP (选择可用性)：网络分区时，允许两边继续写入，事后修复冲突（如 Last-Writer-Wins 或 Vector Clocks）。NoSQL 系统常选这个。

3. 易混点或易错点提示#

• ⚠️ 易错点：不要尝试手动实现 Vector Clocks 让应用层去解决冲突，这非常复杂且容易出错。大多数系统会选择简单的“最后写入者胜”（Last Writer Wins）策略，尽管这可能丢数据。

4. 简短复习小结#

• 网络分区无法避免。
• 银行系统选 CP（不许账目出错）。
• 社交网络点赞选 AP（允许短暂数据不一致，用户体验优先）。

1. 核心概念解释#

在分布式环境中执行 Analytical (OLAP) 查询（尤其是 JOIN）时，最昂贵的开销是网络数据传输。

• Broadcast Join (广播连接)：将小表复制（广播）到所有拥有大表分片的节点上。在本地进行 Join。
• Shuffle Join (洗牌连接)：两张表都很大且未按 Join Key 分片。根据 Join Key 对两张表重新 Hash 分片（Repartition），将相同 Key 的数据推送到同一节点。
• Semi-Join (半连接)：只将 Join 所需的极少量数据（如 Join Key 的列表或 Bloom Filter）发送给另一方，过滤出匹配的行后再传回进行真正的 Join，极大减少网络传输。

2. 关键结论 / 公式 / 方法#

• 开销排序：Shuffle（数据重分布）通常是分布式查询中最大的性能瓶颈。
• 优化策略：尽可能将计算推向数据（Push Query to Data），而不是将数据拉向计算（Pull Data to Query）。

3. 易混点或易错点提示#

• ⚠️ 细节：Semi-Join 虽然减少了网络带宽，但增加了计算步骤（先投影，再传输，再过滤，再回传）。优化器需要权衡计算成本与网络成本。
• ⚠️ 概念：Shuffle Join 和 MapReduce 的逻辑本质上是一样的，MapReduce 实际上是数据库并行执行概念的重新包装。

4. 简短复习小结#

• 小表 Join 大表 -> 用 Broadcast。
• 大表 Join 大表 -> 用 Shuffle。
• 网络带宽极度受限 -> 用 Semi-Join。

🎓 寄语： 分布式数据库的核心在于权衡 (Trade-off)。架构上是 Shared Nothing 的高性能与 Shared Disk 的灵活性之间的权衡；协议上是 2PC 的简单强一致与 Paxos 的高可用之间的权衡；理论上是 CAP 的一致性与可用性之间的权衡。预习和复习时，请重点关注这些权衡背后的原因。祝学习顺利！